// 冒泡排序
function bubble(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

let arr = [1, 2, 3, 4, 6, 7, 5];
console.log(mergeSort(arr));

// 快速排序
function quickSort(arr) {
  if (arr.length < 2) return arr;
  let midIndex = Math.floor(arr.length / 2);
  let midItem = arr.splice(midIndex, 1)[0];
  let left = [],
    right = [];
  arr.forEach((item) => {
    if (item > midItem) {
      right.push(item);
    } else {
      left.push(item);
    }
  });
  return quickSort(left).concat([midItem], quickSort(right));
}

function insertArr(arr) {
  let len = arr.length;
  let temp;
  for (let i = 0; i < arr.length; i++) {
    temp = arr[i];
    for (let j = i; j >= 0; j--) {
      if (arr[j - 1] > temp) {
        arr[j] = arr[j - 1];
      } else {
        arr[j] = temp;
        break;
      }
    }
  }
  return arr;
}

function selectSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let mainItem = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[mainItem] > arr[j]) {
        mainItem = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[mainItem];
    arr[mainItem] = temp;
  }
  return arr;
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return result.concat(left, right);
}

function mergeSort(arr) {
  if (arr.length < 2) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}
